import top100.binarysearch.Solution33;

/**
 * @Author ZhangCuirong
 * @Date 2025/8/4 11:01
 * @description:
 */
public class Solution5 {
    public String longestPalindrome(String s) {
        int maxLen = 1;
        String res = "";
        boolean[][] dp = new boolean[s.length()][s.length()];
        for (int i = 0; i < s.length(); i++) {
            dp[i][i] = true;
            res = s.substring(i, i + 1);
        }
        for (int len = 2; len <= s.length(); len++) {
            for (int i = 0; i < s.length(); i++) {
                int j = i + len - 1;
                if (j < s.length()) {
                    if (s.charAt(i) == s.charAt(j)) {
                        if (len <= 3) {
                            dp[i][j] = true;

                        } else {
                            dp[i][j] = dp[i + 1][j - 1];
                        }
                    }
                    if (dp[i][j]) {
                        if (len > maxLen) {
                            res = s.substring(i, j + 1);
                            maxLen = len;
                        }

                    }
                }
            }
        }
        return res;
    }

    public String longestPalindrome2(String s) {
        String res = "";
        for (int i = 0; i < s.length(); i++) {
            String s1 = palindrome(s, i, i);
            String s2 = palindrome(s, i, i + 1);
            res = res.length() > s1.length() ? res : s1;
            res = res.length() > s2.length() ? res : s2;

        }
        return res;
    }

    String palindrome(String s, int l, int r) {
        while (l > 0 && r < s.length() && s.charAt(l) == s.charAt(r)) {
            l--;
            r++;
        }
        return s.substring(l + 1, r);
    }

    public static void main(String[] args) {
        String s = "bb";
        Solution5 solution = new Solution5();
        String res = solution.longestPalindrome(s);
        System.out.println(res);
    }
}
